# 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
#
#  candidates 中的数字可以无限制重复被选取。
#
#  说明：
#
#
#  所有数字（包括 target）都是正整数。
#  解集不能包含重复的组合。
#
#
#  示例 1：
#
#  输入：candidates = [2,3,6,7], target = 7,
# 所求解集为：
# [
#   [7],
#   [2,2,3]
# ]
#
#
#  示例 2：
#
#  输入：candidates = [2,3,5], target = 8,
# 所求解集为：
# [
#   [2,2,2,2],
#   [2,3,3],
#   [3,5]
# ]
#
#
#
#  提示：
#
#
#  1 <= candidates.length <= 30
#  1 <= candidates[i] <= 200
#  candidate 中的每个元素都是独一无二的。
#  1 <= target <= 500
#
#  Related Topics 数组 回溯算法
#  👍 847 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        #         每个数字可以被重复用

        res = []

        tmp = []

        if len(candidates) == 0:
            return res

        candidates.sort()

        def dfs(candidates, last, target):
            nonlocal tmp, res
            if target == 0:
                res.append(tmp[:])
                return

            for num in candidates:
                # 后面更大的数字不需要继续搜索了
                if num > target:
                    break

                # 不能用前面的数字 比如 用了[2,2,3] 那么后续只能用比 3 大的数字，或者重复用 3
                # 这也是一开始对 candidates 排序的目的
                if num < last:
                    continue
                else:
                    tmp.append(num)
                    dfs(candidates, num, target - num)
                    # 不用当前数字，吐出来，进入下次循环
                    tmp.pop()

        dfs(candidates, candidates[0] - 1, target)
        return res


# leetcode submit region end(Prohibit modification and deletion)

print(Solution().combinationSum([2, 3, 5], 8))
